package pers.tz.题目;

import pers.tz.common.ArrayUtils;

/**
 * @author irony
 * @date 2024-03-15
 */
public class 数组中有多少平方后不同的元素 {
// 给定一个有序数组arr，其中值可能为正、负、0
// 返回ar中每个数都平方之后不同的结果有多少种？

    public static void main(String[] args) {
        int[] ints = ArrayUtils.generateRandomArray(5, true, -10, 10);
        ArrayUtils.printArray(ints);

        System.out.println(countUniqueSquares(ints));
    }

    // 左右双指针解法
    private static int countUniqueSquares(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int start = 0;
        int last = arr.length - 1;
        int ans = 0;

        double prev = -1;

        while (start <= last) {
            double pow1 = Math.pow(arr[start], 2);
            double pow2 = Math.pow(arr[last], 2);
            if (pow1 == pow2) {
                // 跳过连续的情况
                if (pow1 != prev) {
                    ans++;
                    prev = pow1;
                }

                start++;
                last--;
            }
            else if (pow1 > pow2) {
                if (pow1 != prev) {
                    ans++;
                    prev = pow1;
                }
                start++;
            }
            else { // pow1 < pow2
                if (pow2 != prev) {
                    ans++;
                    prev = pow2;
                }
                last--;
            }
        }

        return ans;
    }
}
